package t_1833

import (
	"sort"
)

//夏日炎炎，小男孩 Tony 想买一些雪糕消消暑。
//商店中新到 n 支雪糕，用长度为 n 的数组 costs 表示雪糕的定价，其中 costs[i] 表示第 i 支雪糕的现金价格。
//Tony 一共有 coins 现金可以用于消费，他想要买尽可能多的雪糕。
//给你价格数组 costs 和现金量 coins ，请你计算并返回 Tony 用 coins 现金能够买到的雪糕的 最大数量 。

func maxIceCream(costs []int, coins int) int {

	return caseDp(costs, coins)
}

func caseSort(costs []int, coins int) int {
	count := 0
	sort.Ints(costs)
	for _, v := range costs {
		coins -= v
		if coins <= 0 {
			break
		}
		count++
	}

	return count
}

func caseDp(costs []int, coins int) int {
	dp := make([]int, coins+1)
	for i := 0; i < len(costs); i++ {
		current := make([]int, coins+1)
		for j := 1; j <= coins; j++ {
			current[j] = dp[j] // 不买
			if j >= costs[i] { // 当前雪糕可以买，也可以不买，选择数量最大那种情况
				current[j] = max(dp[j-costs[i]]+1, current[j])
			}
		}
		copy(dp, current)
	}
	return dp[coins]
}

func max(i, j int) int {
	if i > j {
		return i
	}
	return j
}
